package leetcode_400;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 *@author 周杨
 *InsertDeleteGetRandomO1_380 完成一种数据结构 能在O(1)时间复杂度内完成 数据的存入 移除 和返回一个随机数
 *describe:用List保存数 用map保存索引 AC 100%(这里我只用了List AC 4%)
 *2018年7月11日 上午10:45:33
 */
public class InsertDeleteGetRandomO1_380 {
	List<Integer> list;
	/** Initialize your data structure here. */
    public InsertDeleteGetRandomO1_380() {
        this.list=new ArrayList<Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(this.list.contains(val))
        	return false;
        list.add(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!this.list.contains(val))
        	return false;
        Integer i=new Integer(val);
        this.list.remove(i);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int size=this.list.size();
        return this.list.get(new Random().nextInt(size));
    }
}
